//荷兰国旗问题：
int* Netherlands(int arr[], int l, int mid, int r)
{
	//确定小于区间的右边界
	int less = l - 1;
	//确定大于区间的左边界
	int more = r;
	int index = 0;
	while (index < more) {
		if (arr[index] == arr[more]) {
			index++;
		}else if (arr[index] < arr[less]) { //当前数小于<区间就将小于区间的后一个数和当前数的位置交换
			swap(arr[index++], arr[++less]);  
		}else {
			swap(arr[index], arr[--more]);
		}
	}
	swap(arr[more], arr[r]);
	int ret[2];
	ret[0] = less + 1, ret[1] = more;
	
	return ret;
}

void process_qsort(int *arr, int l, int r)
{
	if (l > r) return ;
	int mid = l + ((r - l) >> 1);
	int* tmp = Netherlands(arr, l,mid, r);
	process_qsort(arr, l, tmp[0] - 1);  //递归左区间
	process_qsort(arr, tmp[1] + 1, r);  //递归右区间
}
void func() 
{
	int arr[] = { 6,3,2,1,6,7,485,123,456,3253415,41561,563,12,9,10 };
	int len = sizeof(arr) / sizeof(arr[0]);
	process(arr, 0, len - 1);
	for (auto &ref: arr) {
		cout << ref << " ";
	}
	cout << endl;
}